package com.github.yangyishe.p300;

import java.util.ArrayList;
import java.util.List;

/**
 * 279. 完全平方数
 * https://leetcode.cn/problems/perfect-squares/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 *
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 示例 2：
 *
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 *
 * 提示：
 *
 * 1 <= n <= 104
 */
public class Problem279 {
    public static void main(String[] args) {
        int n=192;

        Problem279 problem279 = new Problem279();
        int numSquares = problem279.numSquares(n);
        System.out.println("numSquares = " + numSquares);

    }

    /**
     * 思路：
     * 提示中已经给出了，按照一维动态规划解决该题。
     * 通过在excel中逐个分析，发现当创建了一个从1开始的最小完全平方和数表之后：
     * 首先维护一个最大平方数原始数n。并计算出下一个最大平方数next=(n+1)^2。
     * 1. 先判断当前数是否==next，如果相等，则直接记录1并继续下一轮即可；
     * 2. 其他情况，必定是小于next，则先获取差值sub=cur-n^2;此时获取到一个候选的最小数量minCount1=1+minCount[sub]
     * 3. 检查sub是否小于（n-1）^2,如果不小于，则minCount1就必定等于要求数；否则再计算第二个差值sub2=cur-(n-1)^2,并计算候补的第二个最小数量minCount2=1+minCount[sub]
     * 4. 检查sub2是否小于(n-2)^2,如果不小于，则实际minCount就等于两个候补minCount的最小值；否则再计算第三个差值sub3=cur-(n-2)^2,
     * 5。继续检查sub3并以此类推。。。
     *
     * cur大于n^2,小于(n+1)^2.
     * (n+1)^2-1-(n-1)^2*2=n^2+2n+1-1-(n^2-2n+1)*2=n^2+2n+1-1-2*n^2+4n-2=-n^2+6n-1=-(n-3)^2+8
     * 以上公式证明还需继续
     *
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        // accList保存之前的平方和，第i个的平方和就是i^2
        List<Integer> accList=new ArrayList<>();
        accList.add(0);
        accList.add(1);
        // 最小数量数组，n就对应minCounts[n]
        int[] minCounts=new int[n+1];
        minCounts[1]=1;
        // 此前最大平方和原始值，供第一时间判断
        int before=1;
        // 下一个最大的平方和，供第一时间判断。同时也会维护到accList中
        int nextAcc=4;
        for(int i=2;i<=n;i++){
            if(i==nextAcc){
                minCounts[i]=1;
                accList.add(nextAcc);
                before++;
                nextAcc=(before+1)*(before+1);
            }else{
                int subSize=1;
                int lastMinCount=Integer.MAX_VALUE;
                while(true){
                    if(accList.size()<subSize+1){
                        minCounts[i]=lastMinCount;
                        break;
                    }
                    int sub=i-accList.get(accList.size()-subSize);
                    int minCount=Integer.min(1+minCounts[sub],lastMinCount);
//                    if(sub>accList.get(accList.size()-subSize)){
//                        minCounts[i]=minCount;
//                        break;
//                    }
                    if(minCount==2){
                        minCounts[i]=minCount;
                        break;
                    }
                    lastMinCount=minCount;
                    subSize++;
                }

            }
        }

        return minCounts[n];
    }
}
